class Solution {
public:
    int d[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    int n, m;
    vector<vector<int>> g;
    
    bool check(int i, int j) {
        if (i >= n || j >= m || i < 0 || j < 0) return false;
        if (g[i][j] == 0) return false;
        return true;
    }
    
    void dfs(int x, int y) {
        g[x][y] = 0;
        for (int i = 0; i < 4; i ++ ) {
            int dx = x + d[i][0], dy = y + d[i][1];
            if (check(dx, dy))
                dfs(dx, dy);
        }    
    }
    
    int numEnclaves(vector<vector<int>>& grid) {
        g = grid;
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                if ((g[i][j] == 1) && (i == 0 || j == 0 || i == n - 1 || j == m - 1))
                    dfs(i, j);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 1)
                    ans ++ ;
        return ans;
    }
};
